#include <iostream>
#include <vector>
using namespace std;


// usse path compression is totally enough! never waste your CODING time and EXECUTION time
// to use a aditional rank array
struct ufs
{
	vector<int> par;
	ufs(int N=0)
		: par(N, -1)
	{
	}

	int get_ans(int i)
	{
		if(par[i]==-1)
			return i;
		int& ret=par[i];
		return ret=get_ans(ret);
	}

	bool same(int x, int y)
	{ return get_ans(x)==get_ans(y); }

	void union_xy(int x, int y)
	{
		x=get_ans(x);
		y=get_ans(y);
		if(x!=y)
			par[x]=y;
	}
};

#include <set>
#include <map>
int main()
{
	ufs u(100);

	for(int i=0;i<50;i++)
		u.union_xy(rand()%100, rand()%100);

	map<int,int> m;
	for(int i=0;i<100;i++)
		m[u.get_ans(i)]++;

	return 0;
}